This invention relates to rule-based artificial intelligence systems (i.e., so-called "expert systems") in which the various conditions defined by the rules are structured as a discrimination net to allow efficient determination of which rules are applicable to data obtained by the system.
An expert system is based on a computer program which comprises a set of rules and defines types of data that will be processed according to the rules. By a process known as "inference", the system performs matching between rules and data in a working data base that is obtained by the system from a user or from other data bases to determine which rules apply, and one or more of these rules is "fired" (i.e., applied to the data) to change the data in the working data base, provide advice to the user or explanations in response to the user's questions, or to take some other action. The inference process is repeated until no rules are found to be applicable to the data, or the firing of rules no longer produces a result.
Each rule includes one or more conditions (collectively referred to as the "left-hand side" of the rule) which, if satisfied by the data, indicate that the rule is applicable. The operations to be performed when the rule is fired are listed in the "right-hand side" of the rule. One way to determine which rules are applicable is to test every condition in the left hand sides of all of the rules each time a new element of data is obtained by the system. With this scheme, conditions that are found satisfied (or not satisfied) by data in the working data base are retested each time the working data base is altered by addition or deletion of data, even if the altered data could not possibly have changed the result of the test. Also, often the same condition is found in the left-hand side of more than one rule, and thus is tested multiple times whenever a new data element is obtained.
To avoid this, some expert systems structure the left-hand sides of the rules as a "discrimination net", such as a so-called "reticular" net or RETE-net. A RETE-net more efficiently determines which rules are applicable by testing, when the working data base is changed, only those conditions having results that may have changed in response to the changed data in the working data base. Also, RETE-nets cause conditions that are common to more than one rule to be tested only once each time the working data base changes.
A RETE-net is a data structure in which the conditions of all rules are arranged as a network of nodes. The conditions of the rules are identified by test nodes that are interconnected by a set of join nodes to represent the various combinations of conditions that are specified in the left-hand sides of the rules. A condition is represented by a single test node, even if that condition occurs in the left-hand sides of multiple rules. Tokens that represent data in the working data base are passed via the nodes through the RETE-net as the data pass various tests and combinations of tests. The RETE-net terminates at result nodes that each correspond to an individual rule. If the left-hand side of a rule is satisfied, the RETE-net stores a token in the result node corresponding to that rule.
RETE-nets work well when the combinations of conditions in the left-hand side of a rule are of the kind that can easily be represented as such a network of nodes. For example, a rule left-hand side that requires condition 1 AND condition 2 AND condition 3 AND condition 4 to be satisfied is represented with an AND node joining the test nodes for conditions 1 and 2, another AND node joining the first AND node and the condition 3 test node, and a third AND node joining the second AND node and the test node for condition 4.
It is often desirable that the left-hand side specify a more flexible combination of conditions, for example: condition 1 AND (at least 2 of: conditions 2, 3, 4, or 5). These types of combinations of conditions are called "meta-tests" and are typically represented by a complex set of nodes which join the condition 1 test node with permutations of the test nodes for conditions 2, 3, 4, and 5, and which terminate at several different result nodes.
It is possible that during an inference cycle the conditions of no rule will be satisfied, but one or more conditions are unsatisfied, not because data is incorrect but because data that would satisfy the condition is missing from the data base. The missing data must be identified and supplied in order to continue.
RETE-net-based expert system programs typically attempt to identify the missing data with special rules that cause the inference process to proceed in the reverse direction (i.e., "backward chaining"), or by asking the user a limited series of questions. In addition, the expert system program may be augmented with special rules (called "null condition" rules) that have conditions which are always satisfied and that are fired only if the left-hand side of no other rule is satisfied. The "actions" taken by null condition rules are selected to help the user recognize that data is needed and to provide a guide for identifying the missing data.